/*
 * subtract.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */
#include <assert.h>
#include "BigInt.h"
using namespace APIAL;

/*
	Perform (result = left - right)
	Result aliasing is ok
	operands can be non-normalized
	left < right is ok
	All pointers must be non-null
	scratchSpace cannot be an alias
*/
void APIAL::Subtract(BigInt *left, BigInt *right, BigInt *result, BigInt *scratchSpace) {
	// Check for addition
	if (left->positive && !right->positive) {
		right->positive = true;
		Add(left, right, result, scratchSpace); 
		right->positive = false;
		return;
	} else if (!left->positive && right->positive) {
		right->positive = false;
		Add(left, right, result, scratchSpace); 
		right->positive = true;
		return;
	}

	// Check for aliasing
	bool resultAlias = (left == result) || (right == result);

	// Normalize
	BigInt::normalize(*left);
	BigInt::normalize(*right);

	// Determine maximum argument
	if ((*left < *right) == left->positive) {
		BigInt *swap = left;
		left = right;
		right = swap;
		result->positive = !left->positive;
	} else {
		result->positive = left->positive;
	}

	// Resize result
	if (result->capacity < left->size) {
		result->resize(left->size, resultAlias);
	}

	// Subtract
	BigInt::subtractNoCheck(left, right, result, 0, left->size);
}

/*
	Perform (result = left - right), although operands are unaligned
	Start from leftChunk (index of most significant chunk), 
		leftBit (bit index), size is leftLength (bits)
	Subtract from rightChunk (index of most significant chunk), 
		rightBit (bit index), size is rightLength (bits)
	Result is aligned with left operand, do not overwrite unaligned
		bits within start and end chunks
	Result does not require resizing
	Alias left = result is ok, right = result is NOT ok
	Operands are normalized
	left >= right
*/
void BigInt::subtractUnaligned(BigInt *left, int leftChunk, int leftBit, int leftLength,
	BigInt *right, int rightChunk, int rightBit, int rightLength,
	BigInt *result) {
	//// Calculate least significant chunk
	//int leftLS = (leftLength-leftBit+left->nonCarryBits-1)/left->nonCarryBits;
	//int leftLSBit = (leftLength+leftBit)%left->nonCarryBits;
	//int rightLS = (rightLength-rightBit+right->nonCarryBits-1)/right->nonCarryBits;
	//int rightLSBit = (rightLength+rightBit)%right->nonCarryBits;
	//int leftShift = leftLSBit-rightLSBit;

	//// Subtract first chunk
	//chunkType temp = left->chunks[leftLS];
	//chunkType rightLSChunk = (right->chunks[rightLS] << leftLSBit) & right->nonCarryBits;

	////result->chunks[leftLS] = 
	
}

/*
	Perform (result = left-right)
	Result aliasing is ok
	Operands are normalized
	left >= right
	start = starting chunk index
	end = ending chunk index (non-inclusive)
*/
void BigInt::subtractNoCheck(BigInt *left, BigInt *right, BigInt *result, int start, int end) {
	// Minimum size must be right->size
	int minSize = right->size;
	if (end < minSize) {
		assert(false);
	}

	// Subtract in parallel
	#pragma omp parallel for
	for (int i = start; i < minSize; i++) {
		result->chunks[i] = left->chunks[i]-right->chunks[i];
	}

	// Ripple the borrow bit until minimum size
	//  If left->size > minSize, copy in value for possible borrow
	if (left->size > minSize) {
		result->chunks[minSize] = left->chunks[minSize];
	}
	for (int i = start; i < minSize; i++) {
		if ((result->chunks[i] >> left->nonCarryBitsMask) != 0) {
			result->chunks[i] &= result->nonCarryBitsMask;
			result->chunks[i+1]--;
		}
	}

	// Copy/ripple until max size
	for (int i = minSize; i < left->size-1; i++) {
		result->chunks[i+1] = left->chunks[i+1];
		if ((result->chunks[i] >> left->nonCarryBitsMask) != 0) {
			result->chunks[i] &= result->nonCarryBitsMask;
			result->chunks[i+1]--;
		}
	}

	// Set result size
	result->size = 0;
	for (int i = end-1; i >= 0; i--) {
		if (result->chunks[i] != 0) {
			result->size = i+1;
			break;
		}
	}

	// Result is normalized
	result->normalized = true;
}

